package com.lg.partition17;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/3/30 10:44
 */
public class P1613跑路_floyd {

    private static final int N = 55, M = 65;
    //f[i][j][k]表示节点i到节点j的距离能否是2^k，如果是，说明能一次性到达
    private static boolean[][][] f = new boolean[N][N][M];
    private static int[][] dist = new int[N][N];
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 0; i < N; i++) Arrays.fill(dist[i], 0x3f3f3f3f);
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]);
            f[a][b][0] = true;
            dist[a][b] = 1;
        }
        for (int k = 1; k <= 64; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    for (int x = 1; x <= n; x++) {
                        if (f[j][i][k - 1] && f[i][x][k - 1]) {
                            f[j][x][k] = true;
                            dist[j][x] = 1;
                        }
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
                }
            }
        }
        writer.write(dist[1][n] + "\n");
        writer.flush();
    }
}
